#include <cstdio>
#include <vector>
#include "trees.h"
#include "tree-algorithms.h"

using namespace std;

int main()
{
	try 
	{
		int n_vertices, n_edges;
		while (true)
		{
			scanf("%d", &n_vertices);
			if ( !n_vertices )
			{
				break;
			}
			scanf("%d", &n_edges);
			vector<Trees::Edge<int> > edges(n_edges);
			for (int i = 0; i < n_edges; i++)
			{
				int v1, v2, cost;
				scanf("%d %d %d", &v1, &v2, &cost);
				edges[i] = Trees::Edge<int>(v1, v2, cost);
			}
			Trees::PathForest<int> f(n_vertices);
			int minMargin = f.MinSpanningTreeMargin(edges);
			printf("%d\n", minMargin);
		}
	} 
	catch (Trees::IllegalTreeOperationException)
	{
		printf("Illegal Tree Operation\n");
		return 1;
	}
	return 0;
}
